package Tree;

import java.util.Map;
import java.util.TreeMap;

/**
 * 题目 ：日程表
 * 题目详述 ：
 * 请实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
 * MyCalendar 有一个 book(int start, int end)方法。
 * 它意味着在 start 到 end 时间内增加一个日程安排，
 * 注意，这里的时间是半开区间，即 [start, end), 实数x 的范围为， start <= x < end。
 * 当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
 * 每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false并且不要将该日程安排添加到日历中。
 * 请按照以下步骤调用 MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
 */
public class MyCalendar {
    /**
     * 核心思想 ：
     * 即，由于所保存的时间区间是不会存在相互重叠的情况；所以只需要去关注开始开始时间即可；
     * （1）判断当前所要插入的时间区间的开始时间 的前一个最大开始时间的时间区间，是否与当前所要插入的时间区间发生重叠，来判断当前时间区间是否能够进行插入；
     * （2）判断当前所要插入的时间区间的开始时间 的后一个最小开始时间的时间区间，是否与当前所要插入的时间区间发生重叠，来判断当前时间区间是否能够进行插入；
     * */
    // 使用TreeMap数据结构：key，用来存放时间区间的开始时间；value，用来存放时间区间的结束时间；
    TreeMap<Integer , Integer> treeMap;
    public MyCalendar() {
        // 初始化TreeMap数据结构
        treeMap = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> Entry = treeMap.floorEntry(start);
        // 时间区间发生重叠的两种情况,即有且仅有在这两种情况之下，才会出现所要插入的时间区间插入失败；
        //（1）前一个时间区间与当前所要插入的时间区间发生重叠
        if(Entry != null && Entry.getValue() > start){
            // 有且仅当（1）所获取的前一个最大开始时间的时间区间不为null；同时，（2）此Entry的value（结束时间）晚于所要插入的时间区间的开始时间
            // 即，代表着这两个时间区间发生重叠；
            return false;
        }
        //（1）后一个时间区间与当前所要插入的时间区间发生重叠
        Entry = treeMap.ceilingEntry(start);
        if(Entry != null && Entry.getKey() < end){
            // 有且仅当（1）所获取的后一个最小开始时间的时间区间不为null；同时，（2）此Entry的key（开始时间）晚于所要插入的时间区间的开始时间
            // 即，代表着这两个时间区间没有发生重叠；
            return false;
        }
        // 若是上述两种情况都不符合的话，即说明当前所要插入的时间区间与之前所保存的时间区间相互之间没有重叠，所以可以直接插入，同时返回true
        treeMap.put(start , end);
        return true;
    }
}
